package leetcode每日一题.leetcode20213;

/**
 * 1. 问题描述
 *      给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
 *
 * 2. 算法分析
 *      问题很简单，但是怎么能够高效的求出和才是关键(暴力当然可以做，并且时间复杂度为线性的，但是从题目的
 *      要求可以看出如果采用暴力，会有冗余的求和)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q001_区域和检索_数组不可变 {
    /**
     * 暴力法实现   复杂度为O(j-i)
     */
    class NumArray1 {

        int[] arr;

        public NumArray1(int[] nums) {
            arr = nums;
        }

        public int sumRange(int i, int j) {
            int res = 0;
            for(int k = i; k <= j; k++) {
                res+=arr[k];
            }
            return res;
        }
    }

    /**
     * 采用前缀和，求出数组前i个元素的和，在初始化的时候求出所以的i的情况
     * 则i到j的和的时间复杂度控制在O(1)
     */
    class NumArray2 {

        int[] prev; // 记录前缀和，prev[i]表示前i个元素的和，可以采用dp来求

        public NumArray2(int[] nums) {
            int n = nums.length;
            if(n == 0) {
                return;
            }
            this.prev = new int[n];
            prev[0] = nums[0];
            for(int i = 1; i < n; i++) {
                prev[i] = prev[i-1] + nums[i];
            }
        }

        public int sumRange(int i, int j) {
            if(i == 0) {
                return prev[j];
            }
            return prev[j] - prev[i] + (prev[i] - prev[i-1]);
        }
    }

    /**
     * 前缀和的优化，我们在设置前缀数组的时候可以将数组的长度设置为n+1，这样可以简化代码
     */
    class NumArray3 {
        int[] sums;

        public NumArray3(int[] nums) {
            int n = nums.length;
            sums = new int[n + 1];
            for (int i = 0; i < n; i++) {
                sums[i + 1] = sums[i] + nums[i];
            }
        }

        public int sumRange(int i, int j) {
            return sums[j + 1] - sums[i];
        }
    }
}
